Search Results

Documents authored by Reisser, Simon


Document
Robustness of Randomized Rumour Spreading

Authors: Rami Daknama, Konstantinos Panagiotou, and Simon Reisser

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
In this work we consider three well-studied broadcast protocols: push, pull and push&pull. A key property of all these models, which is also an important reason for their popularity, is that they are presumed to be very robust, since they are simple, randomized, and, crucially, do not utilize explicitly the global structure of the underlying graph. While sporadic results exist, there has been no systematic theoretical treatment quantifying the robustness of these models. Here we investigate this question with respect to two orthogonal aspects: (adversarial) modifications of the underlying graph and message transmission failures. We explore in particular the following notion of local resilience: beginning with a graph, we investigate up to which fraction of the edges an adversary may delete at each vertex, so that the protocols need significantly more rounds to broadcast the information. Our main findings establish a separation among the three models. On one hand pull is robust with respect to all parameters that we consider. On the other hand, push may slow down significantly, even if the adversary is allowed to modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, push&pull is robust when no message transmission failures are considered, otherwise it may be slowed down. On the technical side, we develop two novel methods for the analysis of randomized rumour spreading protocols. First, we exploit the notion of self-bounding functions to facilitate significantly the round-based analysis: we show that for any graph the variance of the growth of informed vertices is bounded by its expectation, so that concentration results follow immediately. Second, in order to control adversarial modifications of the graph we make use of a powerful tool from extremal graph theory, namely Szemerédi’s Regularity Lemma.

Cite as

Rami Daknama, Konstantinos Panagiotou, and Simon Reisser. Robustness of Randomized Rumour Spreading. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{daknama_et_al:LIPIcs.ESA.2019.36,
  author =	{Daknama, Rami and Panagiotou, Konstantinos and Reisser, Simon},
  title =	{{Robustness of Randomized Rumour Spreading}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.36},
  URN =		{urn:nbn:de:0030-drops-111571},
  doi =		{10.4230/LIPIcs.ESA.2019.36},
  annote =	{Keywords: Rumour Spreading, Local Resilience, Robustness, Self-bounding Functions, Szemer\'{e}di’s Regularity Lemma}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail